//
// Description: 337. 打家劫舍 III
// Created by Loading on 2022/4/10.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

int rob(TreeNode *root) {
    // m1，m2分别表示选中某个节点和未选中某个节点的最大收益
    unordered_map<TreeNode *, int> m1, m2;
    // dfs后序遍历
    function<void(TreeNode *)> dfs = [&](TreeNode *node) {
        if (!node) {
            return;
        }
        dfs(node->left);
        dfs(node->right);
        // 选中node节点，则不能选中其两个左右子节点
        m1[node] = m2[node->left] + m2[node->right] + node->val;
        // 未选中node节点，则两个左右子节点可以选中，也可以不选中
        m2[node] = max(m1[node->left], m2[node->left]) + max(m1[node->right], m2[node->right]);
    };

    dfs(root);
    return max(m1[root], m2[root]);
}

int main() {
    vector<int> nums{3, 2, 3, -1, 3, -1, 1};
    auto root = generateTreeNode(nums);
    auto res = rob(root);
    cout << res << endl;

    return 0;
}